package leetcode.editor.cn.dsa13_mergesort;
// 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
// 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

public class MedianOfTwoSortedArrays4_1 {
    public static void main(String[] args) {
        Solution solution = new MedianOfTwoSortedArrays4_1().new Solution();
        int[] nums1 = {1, 2}, nums2 = {3, 4};
        System.out.println(solution.findMedianSortedArrays(nums1, nums2));
        // 2.5
        int[] nums3 = {2,6,10,15,19}, nums4 = {1,3,8,9,12,16};
        System.out.println(solution.findMedianSortedArrays(nums3, nums4));
        // 9.0
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int m = nums1.length, n = nums2.length;
            // 确保较短的数组在前
            if (m > n) return findMedianSortedArrays(nums2, nums1);
            int p = 0, q = m; // 定义p、q为nums1分界线范围，共m+1个可能的划分位置
            int i = 0, j = 0; // nums1、num2的分界位置(索引)
            // 查找分界线
            while (p <= q) {
                i = (p + q) / 2;  // 二分确定nums1当前分界位置
                // 根据i确定nums2的分界位置，使得左侧元素数-右侧元素数为0或1
                j = (m + n + 1) / 2 - i;
                // nums2左侧的最大值比nums1右侧的最小值要大，说明分界线要右移
                if (j != 0 && i != m && nums2[j - 1] > nums1[i]) {
                    p = i + 1; // nums1划分位置在[i+1, q]之间
                    // nums1左侧的最大值比nums2右侧的最小值要大，说明分界线要左移
                } else if (i != 0 && j != n && nums1[i - 1] > nums2[j]) {
                    q = i - 1; // nums1划分位置在[p, i-1]之间
                } else { // 当前划分位置左侧的最大值小于右侧的最小值，满足要求
                    break;
                }
            }
            // m+n为奇数，返回左侧的最大值
            // 左侧最大值 三种情况：nums1为空、nums2为空、都不为空
            // 左侧nums1为空即i=0，nums2为空即j=0
            int maxLeft = i==0?nums2[j-1]:(j==0?nums1[i-1]:Math.max(nums1[i-1], nums2[j-1]));
            if ((m + n) % 2 == 1) return maxLeft;
            // m+n为偶数，返回左侧最大值与右侧最小值的平均
            // 右侧最小值 三种情况：nums1为空、nums2为空、都不为空
            // 右侧nums1为空即i=m，nums2为空j=n
            int minRight = i==m?nums2[j]:(j==n?nums1[i]:Math.min(nums1[i], nums2[j]));
            return (maxLeft + minRight) / 2.0;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}